A wide variety of types of data can be stored in a database or data structure. When there are many data items or records to be stored, the time needed to access a data item may become undesirably slow. Some data structures contain huge amounts to data. For example, large networks can have millions or billions of destinations and millions of intermediate nodes, and each node may be identified by its own network address.
Traffic in a network may be routed by looking up records in a routing table or structure. The widely-used Internet Protocol, version 4 (IPv4) uses 32-bit IP addresses and can support up to 232 IP nodes, or about 4 billion addresses. A newer version, IPv6, uses 128-bit IP addresses and can have 2128 IP-addressable nodes. Each record in a data structure might contain one IP address or a range of IP addresses.
Routers, switches, and other network nodes may contain a subset of the available IP addresses, and may query other devices for more detailed information. However, the quantity of data records to be stored by a network device can still be quite large, even huge. A network data structure may need to be expandable and able to store all 4 billion possible records, even though only a subset is stored at any time.
An engineering tradeoff often must be made for these large data structures. A single very-large table could be constructed, allowing any record to be retrieved in a fast, single lookup step. However, the size of this table could be enormous, since unused (invalid) entries occupy address locations or slots in the table.
A content-addressable memory (CAM) may also be used for an associative lookup. A CAM may eliminate memory occupied by invalid entries, but CAM's are quite expensive and limited in size. Additionally, a special class of CAM may be required to support range matches. Such a special class of CAM is typically more expensive than a standard exact-match CAM.
The binary search scheme minimizes the memory-space penalty by arranging the entries in a sorted list, and then matching the search key against a value at a mid-point of a partition covering the range that contains the search key. In this approach, the number of accesses can be on the order of log2(N), where N is the number of total entries in the database. However, Log2(N) accesses can be excessive for high-performance applications. Additionally, binary search on a sorted list does not lend itself well for supporting range or longest prefix matches.
A linear binary search may be used on multiple levels of lookup. Each bit of an input lookup key is used to decide between forks in paths through a tree-like table structure. Since multiple levels of search are required, search time is slow, although the storage space needed for the table is more efficient. A traditional Trie structure has a number of access levels equal to a number of bits in the input key. Each stride, or jump to the next level, consumes one bit of the input key.
A compromise data structure modifies the Trie structure to use strides of more than one bit. This structure can provide a good trade-off between access speed and storage requirements. FIG. 1 shows prior-art stride tables in a multi-bit Trie structure. Key 18 is the lookup key that is input to the table structure. A lookup is an operation to find an entry in the table structure that matches key 18.
Key 18 is divided into four strides S1, S2, S3, S3. In this simplified example, key 18 is only 8 bits wide, and each stride is 2 bits wide. Typically much larger keys are used, and the number of strides and width of the strides may vary. Some strides may be larger than other strides.
The first stride S1 selects one of four entries in first-level stride table 10. Entries in table 10 contain pointers to tables 12 in the second level. For example, the top second-level table 12 is pointed to by the top entry in table 10, which is selected when S1 is 11. Another second-level table 12′ is pointed to by the third entry in table 10, which is selected when S1 is 01.
Since each stride is 2 bits, each entry in one level points to a table of 4 entries in the next level. Thus a single table 10 in level 1 expands to four tables 12 in the second level, sixteen tables 14 in the third level, and sixty-four tables 16 in the fourth level.
A lookup is performed by traversing the four levels of the tables in the table structure. For the example of key 18 having a value of 01110011, the first stride S1 is 01 and selects the third entry in table 10, which points to table 12′ in level 2.
The two stride bits 11 for S2 select from among the four entries in each of tables 12. Since first-level stride table 10 pointed to table 12′, an entry from selected table 12′ is used and other tables 12 are ignored. The top entry in table 12′ is selected by the value (11) of S2. This top entry contains a pointer to selected table 14′ in level 3.
The two stride bits S3 of level three select from among the four entries in selected table 14′ in the third level. The value of S3 is 00, which selects the lowest entry in selected table 14′. This entry has a pointer to one of the 64 tables in level four, selected table 16′.
The value of the fourth stride S4, 11, selects the upper of four entries in selected stride table 16′. This entry contains the result of the lookup, or a pointer to the result. The value 01110011 of key 18 returns this result. Both the key and the result may be composed of several fields that are combined together.
When longest-prefix matches (LPM) are supported, intermediate results may be stored in entries in tables 10, 12, 14 of the intermediate levels, rather than only at the end (leaf) levels.
While such Trie structures modified for multi-bit strides are useful compromises between a fast but large single-level table, and a slow but storage-efficient Trie structure, the storage requirements may still be large using stride tables.
Network tables tend to be sparse tables since the address locations are sparsely populated with valid entries. Most memory locations tend to be empty, or have invalid entries. For example, a network router may contain entries for IP addresses within a local area or organization, rather than for the whole Internet. IP addresses outside this local area are sent to a gateway device. A network table for the local-area network router may not need many entries since remote IP addresses are passed off to another device.
Since network tables are sparse, the valid entries in a stride table may be compressed to squeeze our invalid entries and reduce the storage requirements. Ideally, only the valid entries would be stored, but in practice some invalid entries are also stored in the compressed tables. Thus the degree of compression may be less than ideal.
Other types of lookup are known. Five-tuple lookup uses five fields from packet headers to perform the lookup. The five fields are the IP source, IP destination, Protocol type, Port source and Port destination. For IPv4 the resulting key is 104 bits wide, while for IPv6 the key becomes 296 bit wide.
Look-up operations are also performed for Access Control List (ACLs). ACLs consist of rules which indicate what connections are allowed to be made, and which connections are suppressed. There may also be some specifications with respect to Quality-of-Service (QoS) requirements for certain classes of connections. Each entry for ACL may consist of fields that cover a range of values, as opposed to just being exact values.
FIG. 2 shows a prior art compressed stride table. Table 20 is a stride table such as one of tables 10, 12, 14, 16 of FIG. 1. In FIG. 2, the current stride size is 4 bits. The current stride of the input key is used as a 4-bit index address that selects one of the 16 entries in stride table 20. Each entry in stride table 20 is in a location identified by a 4-bit index of bits A3, A2, A1, A0.
Stride table 20 contains only 4 valid entries, at index locations 1100, 1011, 1001, and 1000. The other 12 indexes contain invalid or empty entries.
Since all four valid entries have a 1 in the most-significant-bit (MSB) of the index, or A3=1, index bit A3 is not needed to select among the four valid entries. Index bit A3 could be removed or masked from stride table 20. The entries with A3=0 are deleted, since they are all empty entries. Only the entries with A3=1 are retained in compressed stride table 20′. A 3-bit index is used in compressed stride table 20′ to select among the 8 entries in table 20′.
The size of stride table 20 has been reduced by 50% by eliminating one index bit and deleting the empty entries from compressed stride table 20′. Other stride tables could also be compressed, reducing the overall storage requirements.
While 50% is a significant size reduction, compressed stride table 20′ still has four invalid entries. All three index bits A2, A1, A0 appear to be needed to select one of the four valid entries, since their indexes are now 100, 011, 001, and 000. Each of the three index bits A2, A1, A0 toggle between 0 and 1 within these four entries, so another index bit cannot simply be deleted. For example, if A3 was deleted, then the indexes would be 00, 11, 01, 00. The first and fourth entries would collide, having the same 2-bit index. Since these 2 entries might point to different results or next-level tables, the entries cannot be combined. Thus the maximum compression seems to be 50%, even though half of compressed stride table 20′ is empty or wasted space.
While such compression of stride tables is useful, the resulting compression by masking index bits does not always produce good compression. The resulting compressed stride tables are still somewhat inefficiently compressed.
What is desired is better compression of stride tables. A more flexible and adaptable compression for stride tables is desirable. A lookup engine using compressed stride tables is desirable.